﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0050_Permute : IAlgorithm
    {
        // 46. 全排列

        // 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

        // 提示：
        //  1 <= nums.length <= 6
        //  -10 <= nums[i] <= 10
        //  nums 中的所有整数 互不相同

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 1, 2, 3 };
            // 算法执行与打印
            var result = Permute(nums);
            foreach (var row in result)
            {
                foreach (var item in row)
                {
                    Console.Write(item + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public IList<IList<int>> Permute(int[] nums)
        {
            var res = new List<IList<int>>();
            var path = new List<int>();
            DFS(nums, path, res);
            return res;
        }
        private void DFS(int[] nums, List<int> path, IList<IList<int>> res)
        {
            if (path.Count == nums.Length)
            {
                res.Add(path.ToArray().ToList());
            }
            else
                for (int i = 0; i < nums.Length; i++)
                {
                    if (path.Contains(nums[i]))
                        continue;
                    path.Add(nums[i]);
                    DFS(nums, path, res);
                    path.RemoveAt(path.Count - 1);
                }
        }
    }
}
